package com.zj.sixtyDayChallenge.array;

/**
 * @program: algorithm
 * @description: 对角线遍历
 * 498 diagonal-traverse
 * //给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。
 * //
 * //
 * //
 * // 示例 1：
 * //
 * //
 * //输入：mat = [[1,2,3],[4,5,6],[7,8,9]]
 * //输出：[1,2,4,7,5,3,6,8,9]
 * //
 * //
 * // 示例 2：
 * //
 * //
 * //输入：mat = [[1,2],[3,4]]
 * //输出：[1,2,3,4]
 * //
 * //
 * //
 * //
 * // 提示：
 * //
 * //
 * // m == mat.length
 * // n == mat[i].length
 * // 1 <= m, n <= 10⁴
 * // 1 <= m * n <= 10⁴
 * // -10⁵ <= mat[i][j] <= 10⁵
 * //
 * //
 * // Related Topics 数组 矩阵 模拟 👍 430 👎 0
 * @author: Zhang Bo
 * @create: 2022-01-14 17:05
 **/
public class DiagonalTraverse {
    public static void main(String[] args) {
        Solution solution = new DiagonalTraverse().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] findDiagonalOrder(int[][] mat) {

            if (mat.length == 0 || mat[0].length == 0) {
                return new int[0];
            }

            int n = mat.length;
            int m = mat[0].length;
            int[] res = new int[n * m];
            for (int i = 0, idx = 0; i < n + m - 1; i++) {
                if (i % 2 == 0) {
                    for (int x = Math.min(i, n - 1); x >= Math.max(0, i - m + 1); x--) {
                        res[idx++] = mat[x][i - x];
                    }
                } else {
                    for (int x = Math.max(0, i - m + 1); x <= Math.min(i, n - 1); x++) {
                        res[idx++] = mat[x][i - x];
                    }
                }
            }
            return res;

        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}

